1. Field of the Invention
The present invention relates to a technique for meshing a curved surface that is employed in the fields of analysis of computational dynamics (CAE), NC machining (CAM), building of a three-dimensional shape (CAD), and computer graphics (CG).
2. Related Art
The technique for meshing a curved surface, which divides into a set of triangles a curved surface including a curved shape defined by a parametric curved surface expression, such as a Bezier surface patch or NURBS, has been very important for the above described fields. For example, in the CAE field, the meshing technique is employed for a finite-element method performed by a computer, such as the analysis of a car collision, and in the CAM field, the meshing technique is employed when shaving a curved shape using an NC machine. In the CAD field, the meshing technique is employed for a case wherein a three-dimensional shape is expressed as a set of triangles and a more detailed shape is to be built by repeating the deformation while expending minimum energy. In the CG field, the meshing technique is employed to display a curved surface.
Various methods are employed for meshing a curved surface, and a method that satisfies the following conditions is required.
(1) A trimmed curved surface can be a target for meshing. A trimmed curved surface is a curved shape that is obtained by extracting one necessary part from a curved domain having a triangular or square boundary, such as a Bezier surface patch or NURBS. A shape that has an inside hole is also a trimmed curved surface. Many curved shapes designed by using CAD system are expressed by trimmed curved surfaces, and it is very advantageous to be able to generate meshes relative to a trimmed curved surface.
(2) A complicated curved shape can be processed. It is important to be able to handle a very winding curved shape and a curved shape where two points that are separated by a long interval in parametric space exist close in real space. As a rare case, a self-intersecting curved shape is one example.
(3) Distribution of the sizes of generated elements can be controlled. It is also important that small mesh elements can be generated in an important portion on a curved surface and that large mesh elements can be generated in a portion that is not so important, and that mesh elements that have a distribution in accordance with the curvature of a curved surface can be generated.
(4) A triangular element having a designated shape can be generated. Frequently, required mesh elements have triangular shapes. The triangular shape must be as close to an equilateral triangle as possible. This is because, as well known, when a finite-element analysis method is performed using a mesh that includes extremely distorted elements, it has an adverse effect. Since sometimes an elongated triangle is required, it is also important that a triangle (and/or a square) that is similar to a designated shape can be generated.
(5) The processing should be automatically performed. Although there is a manual meshing method, a desirable method is one for which a pre-process is not required and with which a mesh can be automatically provided by merely inputting the shape type and the mesh distribution.
As a mesh generation method that satisfies the conditions (3) and (5) for a flat surface domain instead of a curved surface, there is a bubble meshing method ("Automatic Mesh Division Using Physical Model," Kenji Shimada, Japanese Simulation Institute, vol. 12, No. 1, 1993, pp. 11-20). The bubble meshing method is a mesh generation method that employs an optimal allocation of mesh nodes, which is obtained by a dynamic calculation, and Delaunay triangular division. An example where the bubble meshing method is applied for a curved surface has been reported ("Comparison of Discretization Algorithms for NURBS Surfaces with Application to Numerically Controlled Machining," S. P. Austin, R. B. Jerard and R. L. Drysdale, Computer Aided Design, Vol. 29, No. 1, 1997, pp. 71-83). In this paper, although the distribution of parameters is not uniform in a normal curved shape, normal Delaunay triangular division is performed in parametric space. As a result, a preferable mesh (mesh that can satisfy the condition (4)) can not be generated on a curved surface in real space. Another paper ("Most Tightly Packing in Sphere and Automatic Triangular Mesh Division of Curved Surface by Delaunay Net," Kenji Shimada, 67th Graphics and CAD Research in Information Processing Institute, 1994, pp. 11-20) describes the movement of a circular or spherical bubble to the optimal position on a curved surface and the adaptive controlling of the number of bubbles on a curved surface. In this paper, since a process for moving a bubble to an optimal position on a curved surface is performed, a process for restricting to a curved surface a bubble whose optimal position is apart from a curved surface because of inter-bubble force is required. In addition, a process concerning three-dimensional space is also required. In the above paper, the previously mentioned condition (4) is not taken into account.
Further, an example for generating an anisotropic mesh having a specific direction has been reported ((1) "Automatic Generation Method For Anisotropic Mesh," Kenji Shimada, 51st (later half of 1997) National Assembly Of Information Processing Institute, 4C-7, 1995; (2) "A Pliant Method For Anisotropic Mesh Generation," F. J. Bossen, P. S. Heckbert, Proceeding of 5th International Meshing Roundrable '96, October 1996, pp. 63-74). According to this method, a vector field indicating a direction and a scalar field indicating the size of a bubble are provided instead of a circular bubble to generate an elliptic bubble, and thus a mesh having a direction is generated. Only a flat surface is described in these papers, and accordingly, no explanation was given for parametric space.
Japanese Unexamined Patent Publication No. Hei 8-315183 describes the filling of a curved surface with the above described elliptic bubble, and suggests the employment of parametric space. In this publication, however, parametric space is employed only to locate first bubbles on a curved surface in real space, and the following process is performed at the curved surface in real space. Since in this publication, as well as for the above paper, a process is performed to move an elliptic bubble to an optimal position on the curved surface, a process is required for restricting to the curved surface, a bubble whose optimal position is outside the curved surface because of internal-bubble force. In addition, a process for three-dimensional space is required. In this publication, it is not obvious that condition (2) is satisfied.
In addition to the above conventional techniques, there are the following techniques.
(a) Method for generating a grid in parametric space is described in "Finite element Mesh Generation Method: A Review And Classification," K. Ho-Le, Computer Aided Designing, Vol. 20, No. 1, 1988, pp. 27-38.
According to this method, a trimmed surface is divided in advance into domains having three sides or four sides, manually or by a specific method, and the domains are divided into grids. Many business analysis software programs employ this method for an associated mesher, but this method does not satisfy the previous mentioned condition (5). Supposing that the mesh generation is performed for all the parts of a single machine, such as a plane or a car, the manual labor required will be enormous. In addition, since the division of domains differs depending on the persons, the resultant meshes are varied depending on the operator. Another problem with the method is the difficulty involved in controlling the size of the mesh elements.
(b) A method using quad-trees is described in: (1) "Comparison Of Discretization Algorithms For NURBS Surfaces With Application To Numerically Controlled Machining," S. P. Austin, R. B. Jerard and R. L. Drysdale, Computer Aided Design, Vol. 29, No. 1, 1997, pp. 71-83; (2) "A Free-Form Mesh Generation For Three-Dimensional Surfaces," T. Hua and I. Zeid, Advances In Design Automation, DE-Col. 65-2, Vol. 2, ASME 1993, pp. 525-534; and (3) "Triangulation Of Trimmed Surfaces In Parametric Space," X. Sheng and B. E. Hirsch, Computer Aided Design, Vol. 24, No. 8, 1992, pp. 437 to 444.
This method recursively divides parametric space into quad-trees. For a trimmed surface, a problem exists in generating a mesh element that is distorted in the vicinity of a border. In particular, in finite element analysis a distorted element that is located at a border of domains would adversely affect the accuracy of an analysis. In addition, a problem with this method is that, even inside the domain, a distorted mesh is generated at a portion at which the number of stages of the quad-trees is changed.
(c) A method for performing triangular mesh generation in real space by using a condition similar to Delaunay conditions is described in (1) "Surface Modeling With Oriented Particle System," R. Szeliski and D. Tonnesen, Computer Graphics, Vol. 26, No. 2, 1992, pp. 185-194; and (2) "Guaranteed-Quality Mesh Generation For Curved Surfaces," L. P. Chew, ACM Symposium On Computational Geometry, 1993, pp. 274-280.
For this method, the condition "consider a sphere that is circumscribed with three mesh nodes on a curved surface and that has its center on the curved surface, and the other mesh nodes are not included inside the sphere" is employed instead of the Delaunay condition "no mesh nodes are included inside a circle that is circumscribed along three mesh nodes on a flat surface." With this method, however, when a curved shape is provided wherein two points are near each other in real space while they are separated by a long interval in parametric space, a mesh that runs the shortest distance in real space is generated, so that mesh generation fails completely. The same problem is also described in "Re-tiling Polygonal Surfaces," T. Turk, Computer Graphics, Vol. 26, No. 2, 1992, pp. 55-64.
(d) A three-dimensional Mesh is described in "Bounded Aspect Ratio Triangulation of Smooth Solids," D. Moore and J. Warren, Symposium On Solid Modeling And Applications, 1991, pp. 455-464.
According to this method, a tetrahedron mesh is generated in a condition where mesh nodes are generated on a curved shape, and finally, mesh nodes other than those on the curved surface are deleted. The division of three-dimensional space into tetrahedrons is not practical, however, because the calculation time is drastically increased compared with that required for triangular division. It is not easy to perform division of tetrahedrons so as to provide a distribution where mesh elements on the curved surface have prescribed sizes.
As described above, there are no conventional methods that satisfy the five previously described conditions.